home *** CD-ROM | disk | FTP | other *** search
/ BBS in a Box 3 / BBS in a box - Trilogy III.iso / Files / Prog / D-G / GemsII / BitCounting / test.c < prev   
Encoding:
C/C++ Source or Header  |  1992-06-16  |  3.5 KB  |  152 lines  |  [TEXT/MPS ]
  1. /*
  2.  * 
  3.  * Here is some code used to test the bit counting algorithms
  4.  * described in "Of Integers, Fields and Bit Counting" by 
  5.  *
  6.  *                         Alan W. Paeth
  7.  *                    NeuralWare Incorporated
  8.  *                   Pittsburgh, Pennsylvania
  9.  *
  10.  *                       David Schilling
  11.  *                     Software Consultant
  12.  *                     Bellevue, Washington
  13.  *
  14.  * It assumes that rand() returns an integer in [0..32767].
  15.  * If long's were returned, the code for generating random samples
  16.  * becomes greatly simplified.
  17.  *
  18.  * srand() is the random seed function.  It is used to produce the
  19.  * SAME random sample each time the test is run so that if bugs are
  20.  * found, they can be reproduced.
  21.  * rand() and srand() are defined in stdlib.h.
  22.  * 
  23.  * Feel free to modify this code for the purposes of tesing the bit
  24.  * counting algorithms on your machine, and also to determine which
  25.  * version is the fastest on your setup.  It is highly recommended
  26.  * that the code which is generated by a compiler for the bit-counting
  27.  * routines be manually examined.
  28.  *
  29.  */
  30.  
  31. #include <stdio.h>
  32. #include <stdlib.h>
  33.  
  34. extern int bit32on1( unsigned long a );
  35. extern int bit32on2( unsigned long a );
  36. extern int bit32on3( unsigned long a );
  37.  
  38. int CorrectCount( unsigned long a )
  39.   {
  40.   int c;
  41.  
  42.   c = 0;
  43.   while( a != 0 )
  44.     {
  45.     c++;
  46.     a = a & ~-a;
  47.     }
  48.   return( c );
  49.   }
  50.  
  51. void Error( unsigned long i, int count, char *fn )
  52.   {
  53.   printf( "\nError: %s( %08lx ) = %d.  Should be %d",
  54.                 fn, i, count, CorrectCount( i ) );
  55.   }
  56.  
  57. test( int (*count)(unsigned long), char *fn )
  58.   {
  59.   unsigned long i;
  60.   unsigned int j, k;
  61.  
  62.   srand( 100 );
  63.  
  64.   printf( "Starting... [%s] \n", fn );
  65.  
  66.   for( j=0; j <= 65000; j++ )            /* first do some random testing. */
  67.     {
  68.     i = ((unsigned long)rand() << 21) ^        /* a random long */
  69.         ((unsigned long)rand() << 17) ^
  70.          (unsigned long)rand();
  71.  
  72.     k = count(i);
  73.  
  74.     if( k != CorrectCount( i ) )
  75.       Error( i, k, fn );
  76.     }
  77.  
  78.   for( j=0; j <= 65000; j++ )            /* test low # of bits */
  79.     {
  80.     i = ( ((unsigned long)rand() << 21) & ((unsigned long)rand() << 21) ) ^
  81.         ( ((unsigned long)rand() << 17) & ((unsigned long)rand() << 17) ) ^
  82.         (  (unsigned long)rand()        & (unsigned long)rand()         );   
  83.  
  84.     k = count(i);
  85.  
  86.     if( k != CorrectCount( i ) )
  87.       Error( i, k, fn );
  88.     }
  89.  
  90.   for( j=0; j <= 65000; j++ )            /* test high # of bits */
  91.     {
  92.     i = ( ((unsigned long)rand() << 21) | ((unsigned long)rand() << 21) ) ^
  93.         ( ((unsigned long)rand() << 17) | ((unsigned long)rand() << 17) ) ^
  94.         (  (unsigned long)rand()        | (unsigned long)rand()         );   
  95.  
  96.     k = count(i);
  97.  
  98.     if( k != CorrectCount( i ) )
  99.       Error( i, k, fn );
  100.     }
  101.  
  102.  
  103.  
  104.   i = 1L;                    /* Now try all permutations */
  105.   for( j =0; j < 33; j++ )            /* with only 1 bit. */
  106.     {                        /* termination includes all 0s */
  107.     k = count(i);
  108.     if( i != 0 )
  109.       {
  110.       if( k != 1 )
  111.         Error( i, k, fn );
  112.       }
  113.     else
  114.       {
  115.       if( k != 0 )
  116.         Error( i, k, fn );
  117.       }
  118.     i <<= 1;
  119.     }
  120.  
  121.   i = 1L;                    /* Finally, all permutations */
  122.   for( j =0; j < 33; j++ )            /* with only one 0 bit. */
  123.     {                        /* termination includes all 1s */
  124.     k = count( ~i );
  125.     if( i != 0 )
  126.       {
  127.       if( k != 31 )
  128.         Error( ~i, k, fn );
  129.       }
  130.     else
  131.       {
  132.       if( k != 32 )
  133.         Error( ~i, k, fn );
  134.       }
  135.     i <<= 1;
  136.     }
  137.  
  138.   printf( "... Done.\n" );
  139.   }
  140.  
  141.  
  142. void main( void )
  143.   {
  144.   test( bit32on1, "bit32on1" );
  145.   test( bit32on2, "bit32on2" );
  146.   test( bit32on3, "bit32on3" );
  147.   }
  148.  
  149.  
  150.  
  151.  
  152.